# 砌砖： https://leetcode-cn.com/problems/brick-wall/

# 暴力破解，超时
class Solution:
    def leastBricks(self, wall: list) -> int:
        """
            暴力解法，实际上问题抽象出来就是， 找到同一数值target位置，相同和最多的。
            每一行前面和 等于 target越多，被串的就越少，越理想
        """
        # 墙的宽度
        total = sum(wall[0])
        # 总层数
        rows = len(wall)

        # 最终不被穿过的层数
        rst = 0
        # 遍历墙宽范围内的所有位置
        for i in range(1, total):
            n = 0
            # 统计每行会不会被穿过
            for row in wall:
                count = 0
                # 本行是否有等于 指定位置值的
                for j in row:
                    count += j
                    if count == i:
                        n += 1
                        break
                    elif count > i:
                        break

            # 统计哪个数值，不被穿过的层最多
            rst = max(n, rst)    
        
        # 返回被穿的层数为 总层数 - 不被穿层数
        return rows - rst


# (通过)： 根据暴力破解的思路优化，利用字典进行统计，前n块砖切割有多少不被穿过， 找到最大值，总层数减去 最大值，就是最少被穿过的
class Solution:
    def leastBricks(self, wall: list) -> int:
        """
            利用暴力破解的思想，我们用空间换取时间，使用 字典来统计每个宽度有多少不用穿过,并且根据砖的长度，不需要枚举每一单位
        """
        widthCount = dict()
        rows = len(wall)
        for row in wall:
            length = 0
            # 统计距离墙左边，n 块砖的距离，有哪些不被穿过
            for i in range(0, len(row)-1):
                # 这个位置砖块距离墙左边的长度
                length += row[i]
                # widthCount[length] = widthCount.get(length, 0) + 1, 可以优化掉if else
                if length in widthCount:
                    widthCount[length] += 1
                else:
                    widthCount[length] = 1

        rst = 0   
        # 找出最大不被穿过的值
        for count in widthCount.values():
            rst = max(count, rst)

        return rows - rst




